package com.dexter.year2023.charpter2_reverselinklist.level2.topic2_3单链表加1;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import java.util.Stack;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;
import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.printLinkedList;

/**
 * LeetCode 369. 给单链表加1
 * https://leetcode.cn/problems/plus-one-linked-list/ 🔒
 *
 * @author Dexter
 */
public class PlusOne {
    /**
     * 输入 [1,2,3]
     * 输出 [1,2,4]
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        Node head = initLinkedList(a);
        int testMethod = 1;
        Node newHead = null;
        switch (testMethod) {
            case 1:
                // 法1：用Stack（进阶）
                newHead = plusOneByStack(head);
                break;
            case 2:
                // 法2：两次反转链表
                newHead = plusOneByReverse(head);
                break;
            default:
                System.out.println("测试方法超出范围");
                break;
        }

        printLinkedList(newHead);
    }

    /**
     * 法1：用Stack实现，sum新结点反转
     *
     * @param head
     * @return
     */
    public static Node plusOneByStack(Node head) {
        // 入栈
        Stack<Integer> st = new Stack<>();
        while (head != null) {
            st.push(head.val);
            head = head.next;
        }
        // 进位
        int carry = 0;
        // 加1
        int adder = 1;
        // 新的链表
        Node dummy = new Node(-1);
        // 出栈
        while (!st.empty() || carry > 0) {
            int digit = st.empty() ? 0 : st.pop();
            int sum = digit + adder + carry;
            carry = sum / 10;
            sum = sum % 10;
            Node cur = new Node(sum);
            // 反转链表
            cur.next = dummy.next;
            dummy.next = cur;
            adder = 0;
        }
        return dummy.next;
    }

    /**
     * 法2：链表反转，两次（作业）
     *
     * @param head
     * @return
     */
    public static Node plusOneByReverse(Node head) {
        // 拿到链表，第一次反转
        head = reverseList(head);
        // 新的链表
        Node dummy = new Node(-1);
        Node cur = dummy;
        int carry = 0;
        int adder = 1;
        while (head != null) {
            int sum = head.val + adder + carry;
            carry = sum / 10;
            sum = sum % 10;
            cur.next = new Node(sum);
            // 往后移一位，要饭盆
            cur = cur.next;
            head = head.next;
            adder = 0;
        }
        // 循环结束后，第二次反转
        return reverseList(dummy.next);
    }

    private static Node reverseList(Node head) {
        // 8行代码
        Node cur = head;
        Node pre = null;
        while (cur != null) {
            Node next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
